package leetcode.pre100;

import utils.ListNode;
import utils.ListUtil;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个链表和一个特定值 x，对链表进行分隔，
 *
 * 使得所有小于 x 的节点都在大于或等于 x 的节点之前。
 * <p>
 *
 * <p>
 * 示例:
 * <p>
 * 输入: head = 1->4->3->2->5->2, x = 3
 * 输出: 1->2->2->4->3->5
 * <p>
 *
 * 进阶1：你应当保留两个分区中每个节点的初始相对位置。
 *
 * 进阶2：{@link baseclass.d_list.Code04_NetherFlagList}
 *
 * @date 2020/6/8 16:33
 */
public class Code86_NetherFlagList_分隔链表 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(4);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(2);
        head = partition(head,3);
        ListUtil.printLinkedList(head);
    }
    /**
     * 方式1：把链表的值放入数组，给数组partition
     */
    public static ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        List<ListNode> list = new LinkedList<>();
        ListNode p = head;
        while (p != null) {
            list.add(p);
            p = p.next;
        }
        doPartition(list, x);
        head = p = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            p.next = list.get(i);
            p = p.next;
        }
        p.next = null;
        return head;
    }

    private static void doPartition(List<ListNode> list, int x) {
        int less = -1;
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).val < x) {
                Collections.swap(list, ++less, i);
            }
        }
    }
    /**
     *  进阶1：保留大于或小于部分的相对顺序，不能用partition
     */
    public static ListNode partition2(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        List<ListNode> list = new LinkedList<>();
        ListNode p = head;
        //先存小于x的
        while (p != null) {
            if(p.val < x)
                list.add(p);
            p = p.next;
        }
        //再存大于等于x的
        p = head;
        while (p != null) {
            if(p.val >= x)
                list.add(p);
            p = p.next;
        }
        head = p = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            p.next = list.get(i);
            p = p.next;
        }
        p.next = null;
        return head;
    }

    /**
     * 进阶2：实用空间复杂度是O(1)
     */
    public static ListNode partition3(ListNode head, int x) {
        //
        if (head == null || head.next == null) return head;
        ListNode p = head;
        ListNode smallH = null;
        ListNode smallT = null;
        ListNode bigH = null;
        ListNode bigT = null;
        while (p != null){
            ListNode next = p.next;
            //把p断开
            p.next = null;
            if(p.val < x){
                if(smallH == null){
                    smallH = p;
                    smallT = p;
                }else {
                    smallT.next = p;
                    smallT = p;
                }
            }else {
                if(bigH == null){
                    bigH = p;
                    bigT = p;
                }else {
                    bigT.next = p;
                    bigT = p;
                }
            }
            p = next;
        }
        //把两部分连起来
        if(smallH == null)
            return bigH;
        smallT.next = bigH;
        return smallH;
    }
}
